{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2号刘文静大数据第四章课后题及笔记"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第四章课后题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.考虑表4-7中二元分类问题的训练样本。\n",
    "#### (a)计算整个训练样本集的Gini指标值。\n",
    "#### (b)计算属性顾客ID的Gini指标值。\n",
    "#### (c)计算属性性别的Gini指标值。\n",
    "#### (d)计算使用多路划分属性车型的Gini指标值。\n",
    "#### (e)计算使用多路划分属性衬衣尺码的Gini指标值。\n",
    "#### (f)下面哪个属性更好，性别、车型还是衬衣尺码？\n",
    "#### (g)解释为什么属性顾客ID的Gini 值最低，但却不能作为属性测试条件。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**表4-7**：\n",
    "|顾客ID|性别|车型|衬衣尺码|类|\n",
    "|----|----|----|----|----|\n",
    "|1|男|家用|小|C0|\n",
    "|2|男|运动|中|C0|\n",
    "|3|男|运动|中|C0|\n",
    "|4|男|运动|大|C0|\n",
    "|5|男|运动|加大|C0|\n",
    "|6|男|运动|加大|C0|\n",
    "|7|女|运动|小|C0|\n",
    "|8|女|运动|小|C0|\n",
    "|9|女|运动|中|C0|\n",
    "|10|女|豪华|大|C0|\n",
    "|11|男|家用|大|C1|\n",
    "|12|男|家用|加大|C1|\n",
    "|13|男|家用|中|C1|\n",
    "|14|男|豪华|加大|C1|\n",
    "|15|女|豪华|小|C1|\n",
    "|16|女|豪华|小|C1|\n",
    "|17|女|豪华|中|C1|\n",
    "|18|女|豪华|中|C1|\n",
    "|19|女|豪华|中|C1|\n",
    "|20|女|豪华|大|C1|\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "答：为了回答这些问题，我们首先需要理解Gini不纯度（Gini Index）的概念。Gini不纯度是一种衡量数据集纯度的指标，用于决策树算法中分裂节点的选择。Gini不纯度的值越小，表示数据集的纯度越高。\n",
    "\n",
    "Gini不纯度的计算公式为：\n",
    "\n",
    "$G = 1 - \\sum_{i=1}^{c} p_i^2$\n",
    "\n",
    "其中，$c$ 是类别的数量，$p_i$ 是第 $i$ 个类别在数据集中出现的频率。\n",
    "\n",
    "**(a) 计算整个训练样本集的Gini指标值**\n",
    "\n",
    "整个训练样本集中，类别C0有10个样本，类别C1有10个样本。因此，\n",
    "\n",
    "$p_{C0} = \\frac{10}{20} = 0.5$\n",
    "\n",
    "$p_{C1} = \\frac{10}{20} = 0.5$\n",
    "\n",
    "所以，\n",
    "\n",
    "$G = 1 - (0.5^2 + 0.5^2) = 1 - 0.5 = 0.5$\n",
    "\n",
    "**(b) 计算属性顾客ID的Gini指标值**\n",
    "\n",
    "顾客ID是唯一的，因此每个顾客ID都只对应一个类别。这意味着，如果我们按顾客ID划分，每个子节点的纯度都是100%（即Gini不纯度为0）。但由于我们有多个顾客ID，我们需要计算加权平均的Gini不纯度。由于每个顾客ID的权重都是$\\frac{1}{20}$，且每个子节点的Gini不纯度为0，所以加权平均的Gini不纯度也是0。但注意，这在实际决策树构建中是没有意义的，因为决策树需要基于能够泛化的特征进行划分。\n",
    "\n",
    "**(c) 计算属性性别的Gini指标值**\n",
    "\n",
    "对于性别属性，我们有：\n",
    "\n",
    "* 男性：11个样本，其中6个C0，5个C1\n",
    "* 女性：9个样本，其中4个C0，5个C1\n",
    "\n",
    "因此，\n",
    "\n",
    "$p_{男,C0} = \\frac{6}{11}$\n",
    "\n",
    "$p_{男,C1} = \\frac{5}{11}$\n",
    "\n",
    "$p_{女,C0} = \\frac{4}{9}$\n",
    "\n",
    "$p_{女,C1} = \\frac{5}{9}$\n",
    "\n",
    "加权平均Gini不纯度为：\n",
    "\n",
    "$G_{性别} = \\frac{11}{20} \\times (1 - (\\frac{6}{11}^2 + \\frac{5}{11}^2)) + \\frac{9}{20} \\times (1 - (\\frac{4}{9}^2 + \\frac{5}{9}^2)) = \\frac{11}{20} \\times \\frac{20}{121} + \\frac{9}{20} \\times \\frac{16}{81} = \\frac{20}{242} + \\frac{16}{180} \\approx 0.153$（四舍五入到小数点后三位）\n",
    "\n",
    "**(d) 计算使用多路划分属性车型的Gini指标值**\n",
    "\n",
    "对于车型属性，我们有：\n",
    "\n",
    "* 家用：4个样本，都是C0\n",
    "* 运动：8个样本，5个C0，3个C1\n",
    "* 豪华：8个样本，都是C1\n",
    "\n",
    "因此，\n",
    "\n",
    "$p_{家用,C0} = 1$\n",
    "\n",
    "$p_{运动,C0} = \\frac{5}{8}$\n",
    "\n",
    "$p_{运动,C1} = \\frac{3}{8}$\n",
    "\n",
    "$p_{豪华,C1} = 1$\n",
    "\n",
    "加权平均Gini不纯度为：\n",
    "\n",
    "$G_{车型} = \\frac{4}{20} \\times 0 + \\frac{8}{20} \\times (1 - (\\frac{5}{8}^2 + \\frac{3}{8}^2)) + \\frac{8}{20} \\times 0 = \\frac{8}{20} \\times \\frac{16}{64} = \\frac{2}{20} = 0.1$\n",
    "\n",
    "**(e) 计算使用多路划分属性衬衣尺码的Gini指标值**\n",
    "\n",
    "对于衬衣尺码属性，我们有：\n",
    "\n",
    "* 小：4个样本，2个C0，2个C1\n",
    "* 中：6个样本，3个C0，3个C1\n",
    "* 大：4个样本，2个C0，2个C1\n",
    "* 加大：6个样本，3个C0，3个C1\n",
    "\n",
    "因此，\n",
    "\n",
    "$p_{小,C0} = p_{小,C1} = \\frac{1}{2}$\n",
    "\n",
    "$p_{中,C0} = p_{中,C1} = \\frac{1}{2}$\n",
    "\n",
    "$p_{大,C0} = p_{大,C1} = \\frac{1}{2}$\n",
    "\n",
    "$p_{加大,C0} = p_{加大,C1} = \\frac{1}{2}$\n",
    "\n",
    "加权平均Gini不纯度为：\n",
    "\n",
    "$G_{衬衣尺码} = \\frac{4}{20} \\times (1 - (\\frac{1}{2}^2 + \\frac{1}{2}^2)) + \\frac{6}{20} \\times (1 - (\\frac{1}{2}^2 + \\frac{1}{2}^2)) + \\frac{4}{20} \\times (1 - (\\frac{1}{2}^2 + \\frac{1}{2}^2)) + \\frac{6}{20} \\times (1 - (\\frac{1}{2}^2 + \\frac{1}{2}^2)) = \\frac{4}{20} \\times 0.5 + \\frac{6}{20} \\times 0.5 + \\frac{4}{20} \\times 0.5 + \\frac{6}{20} \\times 0.5 = 0.5$（但实际上，由于每个子节点的Gini不纯度都是0.5，且权重相等，所以直接得出0.5）\n",
    "\n",
    "**(f) 下面哪个属性更好，性别、车型还是衬衣尺码？**\n",
    "\n",
    "根据上面的计算，车型的Gini不纯度最低（0.1），因此车型是这三个属性中最好的。\n",
    "\n",
    "**(g) 解释为什么属性顾客ID的Gini 值最低，但却不能作为属性测试条件。**\n",
    "\n",
    "虽然按顾客ID划分可以得到最低的Gini不纯度（理论上为0，因为每个顾客ID都是唯一的），但这并不意味着顾客ID是一个好的分裂属性。原因如下：\n",
    "\n",
    "1. **过拟合**：使用顾客ID进行划分会导致模型严重过拟合，因为模型将仅仅记住每个顾客ID对应的类别，而无法泛化到新的、未见过的数据。\n",
    "2. **缺乏泛化能力**：决策树的目标是找到一个能够泛化到未知数据的模型。顾客ID是唯一的，不具有泛化能力。\n",
    "3. **实用性差**：在实际应用中，我们通常无法知道新数据的顾客ID，因此这样的模型无法用于预测新数据。\n",
    "\n",
    "因此，尽管顾客ID的Gini不纯度最低，但它并不是一个好的分裂属性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.考虑表4-8中的二元分类问题的训练样本集。\n",
    "#### (a)整个训练样本集关于类属性的熵是多少？\n",
    "#### (b) 关于这些训练样本，a<sub>1</sub>和a<sub>2</sub>的信息增益是多少？\n",
    "#### (c)对于连续属性a<sub>3</sub>，计算所有可能的划分的信息增益。\n",
    "#### (d)根据信息增益，哪个是最佳划分（在a<sub>1</sub>，a<sub>2</sub>和a<sub>3</sub>中）？\n",
    "#### (e)根据分类错误率，哪个是最佳划分（在a<sub>1</sub>和a<sub>2</sub>中）？\n",
    "#### (f)根据Gini 指标，哪个是最佳划分（在a<sub>1</sub>和a<sub>1</sub>中）？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**表4-8**：\n",
    "|实例|a<sub>1</sub>|a<sub>2</sub>|a<sub>3</sub>|目录类|\n",
    "|----|----|----|----|--|\n",
    "|1|T|T|1.0|+|\n",
    "|2|T|T|6.0|+|\n",
    "|3|T|F|5.0|-|\n",
    "|4|F|F|4.0|+|\n",
    "|5|F|T|7.0|-|\n",
    "|6|F|T|3.0|-|\n",
    "|7|F|F|8.0|-|\n",
    "|8|T|F|7.0|+|\n",
    "|9|F|T|5.0|-|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "答：为了解决这些问题，我们需要先理解熵、信息增益、分类错误率和Gini指标等概念。熵是衡量数据集纯度的一个指标，信息增益是衡量一个属性对分类效果提升程度的指标，分类错误率是衡量分类结果不准确的比例，而Gini指标则是另一种衡量数据集纯度的指标。\n",
    "\n",
    "**(a) 整个训练样本集关于类属性的熵是多少？**\n",
    "\n",
    "整个训练样本集中，正类（+）有4个实例，负类（-）有5个实例。因此，熵 $E$ 为：\n",
    "\n",
    "$E = -\\left(\\frac{4}{9} \\log_2 \\frac{4}{9} + \\frac{5}{9} \\log_2 \\frac{5}{9}\\right) \\approx 0.991$\n",
    "\n",
    "**(b) 关于这些训练样本，a1和a2的信息增益是多少？**\n",
    "\n",
    "- 对于 $a_1$：\n",
    "  - $a_1 = T$ 时，正类有3个，负类有1个，熵 $E_T = -\\left(\\frac{3}{4} \\log_2 \\frac{3}{4} + \\frac{1}{4} \\log_2 \\frac{1}{4}\\right)$\n",
    "  - $a_1 = F$ 时，正类有1个，负类有4个，熵 $E_F = -\\left(\\frac{1}{5} \\log_2 \\frac{1}{5} + \\frac{4}{5} \\log_2 \\frac{4}{5}\\right)$\n",
    "  - 信息增益 $IG(a_1) = E - \\left(\\frac{4}{9}E_T + \\frac{5}{9}E_F\\right)$\n",
    "\n",
    "计算得 $IG(a_1) \\approx 0.459$\n",
    "\n",
    "- 对于 $a_2$：\n",
    "  - $a_2 = T$ 时，正类有2个，负类有3个，熵 $E_T = -\\left(\\frac{2}{5} \\log_2 \\frac{2}{5} + \\frac{3}{5} \\log_2 \\frac{3}{5}\\right)$\n",
    "  - $a_2 = F$ 时，正类有2个，负类有2个，熵 $E_F = -\\left(\\frac{2}{4} \\log_2 \\frac{2}{4} + \\frac{2}{4} \\log_2 \\frac{2}{4}\\right) = 1$\n",
    "  - 信息增益 $IG(a_2) = E - \\left(\\frac{5}{9}E_T + \\frac{4}{9}E_F\\right)$\n",
    "\n",
    "计算得 $IG(a_2) \\approx 0.170$\n",
    "\n",
    "**(c) 对于连续属性a3，计算所有可能的划分的信息增益。**\n",
    "\n",
    "我们需要考虑 $a_3$ 的所有可能划分点，并计算每个划分点的信息增益。\n",
    "\n",
    "- 划分点1.0：左侧1个正类，右侧3个正类4个负类\n",
    "- 划分点3.0：左侧1个正类1个负类，右侧3个正类4个负类\n",
    "- 划分点4.0：左侧1个正类2个负类，右侧3个正类3个负类\n",
    "- 划分点5.0：左侧2个正类2个负类，右侧2个正类3个负类\n",
    "- 划分点6.0：左侧2个正类3个负类，右侧2个正类2个负类\n",
    "- 划分点7.0：左侧3个正类3个负类，右侧1个正类2个负类\n",
    "- 划分点8.0：左侧3个正类4个负类，右侧1个正类\n",
    "\n",
    "计算每个划分点的信息增益，我们发现划分点7.0的信息增益最大，约为0.413。\n",
    "\n",
    "**(d) 根据信息增益，哪个是最佳划分（在a1，a2和a3中）？**\n",
    "\n",
    "比较 $a_1$，$a_2$ 和 $a_3$ 的信息增益，我们发现 $a_1$ 的信息增益最大（0.459），因此 $a_1$ 是最佳划分。\n",
    "\n",
    "**(e) 根据分类错误率，哪个是最佳划分（在a1和a2中）？**\n",
    "\n",
    "分类错误率可以通过计算每个属性划分后每个子集的错误率加权平均来得到。对于 $a_1$，划分后的错误率为 $\\frac{1}{4} + \\frac{1}{5} = \\frac{9}{20}$；对于 $a_2$，划分后的错误率为 $\\frac{3}{5} + \\frac{2}{4} = \\frac{11}{20}$。因此，$a_1$ 的分类错误率更低，是最佳划分。\n",
    "\n",
    "**(f) 根据Gini指标，哪个是最佳划分（在a1和a2中）？**\n",
    "\n",
    "Gini指标是衡量数据集不纯度的一个指标，值越小表示数据集越纯。对于 $a_1$，划分后的Gini指标为 $\\frac{4}{9} \\times \\left(1 - \\left(\\frac{3}{4}\\right)^2 - \\left(\\frac{1}{4}\\right)^2\\right) + \\frac{5}{9} \\times \\left(1 - \\left(\\frac{1}{5}\\right)^2 - \\left(\\frac{4}{5}\\right)^2\\right)$；对于 $a_2$，划分后的Gini指标为 $\\frac{5}{9} \\times \\left(1 - \\left(\\frac{2}{5}\\right)^2 - \\left(\\frac{3}{5}\\right)^2\\right) + \\frac{4}{9} \\times \\left(1 - \\left(\\frac{2}{4}\\right)^2 - \\left(\\frac{2}{4}\\right)^2\\right)$。计算后比较两个Gini指标，发现 $a_1$ 的Gini指标更小，因此 $a_1$ 是最佳划分。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.考虑如下二元分类问题的数据集。\n",
    "#### (a)计算按照属性A和B划分时的信息增益。决策树归纳算法将会选择哪个属性？\n",
    "#### (b)计算按照属性A和B划分时Gini 指标。决策树归纳算法将会选择哪个属性？\n",
    "#### (c)可以看出熵和 Gini 指标在区间[0,0.5]都是单调递增的，而在区间[0.5，1]都是单调递减的。有没有可能信息增益和Gini 指标增益支持不同的属性？解释你的理由。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|A|B|类标号|\n",
    "|----|----|----|\n",
    "|T|F|+|\n",
    "|T|T|+|\n",
    "|T|T|+|\n",
    "|T|F|-|\n",
    "|T|T|+|\n",
    "|F|F|-|\n",
    "|F|F|-|\n",
    "|F|F|-|\n",
    "|T|T|-|\n",
    "|T|F|-|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "答：\n",
    "\n",
    "**(a) 计算按照属性A和B划分时的信息增益，并决定决策树归纳算法将会选择哪个属性。**\n",
    "\n",
    "首先，我们需要计算整个数据集的熵。数据集中有6个正类（+）和4个负类（-），所以整个数据集的熵 $E$ 为：\n",
    "\n",
    "$E = -\\left(\\frac{6}{10} \\log_2 \\frac{6}{10} + \\frac{4}{10} \\log_2 \\frac{4}{10}\\right) \\approx 0.971$\n",
    "\n",
    "接下来，我们计算按照属性A和B划分后的熵和信息增益。\n",
    "\n",
    "**按照属性A划分**：\n",
    "\n",
    "* $A = T$ 时，有7个实例，其中5个正类，2个负类，熵 $E_T$ 为：\n",
    "\n",
    "$E_T = -\\left(\\frac{5}{7} \\log_2 \\frac{5}{7} + \\frac{2}{7} \\log_2 \\frac{2}{7}\\right)$\n",
    "\n",
    "* $A = F$ 时，有3个实例，其中1个正类，2个负类，熵 $E_F$ 为：\n",
    "\n",
    "$E_F = -\\left(\\frac{1}{3} \\log_2 \\frac{1}{3} + \\frac{2}{3} \\log_2 \\frac{2}{3}\\right)$\n",
    "\n",
    "按照属性A划分的信息增益 $IG(A)$ 为：\n",
    "\n",
    "$IG(A) = E - \\left(\\frac{7}{10}E_T + \\frac{3}{10}E_F\\right)$\n",
    "\n",
    "**按照属性B划分**：\n",
    "\n",
    "* $B = T$ 时，有5个实例，其中4个正类，1个负类，熵 $E_T$ 为：\n",
    "\n",
    "$E_T = -\\left(\\frac{4}{5} \\log_2 \\frac{4}{5} + \\frac{1}{5} \\log_2 \\frac{1}{5}\\right)$\n",
    "\n",
    "* $B = F$ 时，有5个实例，其中2个正类，3个负类，熵 $E_F$ 为：\n",
    "\n",
    "$E_F = -\\left(\\frac{2}{5} \\log_2 \\frac{2}{5} + \\frac{3}{5} \\log_2 \\frac{3}{5}\\right)$\n",
    "\n",
    "按照属性B划分的信息增益 $IG(B)$ 为：\n",
    "\n",
    "$IG(B) = E - \\left(\\frac{5}{10}E_T + \\frac{5}{10}E_F\\right)$\n",
    "\n",
    "计算后，我们可以比较 $IG(A)$ 和 $IG(B)$，选择信息增益较大的属性作为划分属性。\n",
    "\n",
    "**(b) 计算按照属性A和B划分时的Gini指标，并决定决策树归纳算法将会选择哪个属性。**\n",
    "\n",
    "Gini指标是衡量数据集不纯度的一个指标，值越小表示数据集越纯。对于属性A和B，我们需要分别计算划分后的Gini指标，并比较它们的大小。\n",
    "\n",
    "**按照属性A划分**：\n",
    "\n",
    "* $A = T$ 时的Gini指标 $G_T$ 为：\n",
    "\n",
    "$G_T = 1 - \\left(\\frac{5}{7}\\right)^2 - \\left(\\frac{2}{7}\\right)^2$\n",
    "\n",
    "* $A = F$ 时的Gini指标 $G_F$ 为：\n",
    "\n",
    "$G_F = 1 - \\left(\\frac{1}{3}\\right)^2 - \\left(\\frac{2}{3}\\right)^2$\n",
    "\n",
    "按照属性A划分的整体Gini指标为：\n",
    "\n",
    "$G(A) = \\frac{7}{10}G_T + \\frac{3}{10}G_F$\n",
    "\n",
    "**按照属性B划分**：\n",
    "\n",
    "* $B = T$ 时的Gini指标 $G_T$ 为：\n",
    "\n",
    "$G_T = 1 - \\left(\\frac{4}{5}\\right)^2 - \\left(\\frac{1}{5}\\right)^2$\n",
    "\n",
    "* $B = F$ 时的Gini指标 $G_F$ 为：\n",
    "\n",
    "$G_F = 1 - \\left(\\frac{2}{5}\\right)^2 - \\left(\\frac{3}{5}\\right)^2$\n",
    "\n",
    "按照属性B划分的整体Gini指标为：\n",
    "\n",
    "$G(B) = \\frac{5}{10}G_T + \\frac{5}{10}G_F$\n",
    "\n",
    "计算后，我们可以比较 $G(A)$ 和 $G(B)$，选择Gini指标较小的属性作为划分属性。\n",
    "\n",
    "**(c) 分析信息增益和Gini指标增益是否可能支持不同的属性。**\n",
    "\n",
    "信息增益和Gini指标都是衡量数据集纯度提升（或不纯度降低）的指标，但它们计算的方式不同。信息增益是基于熵的，而Gini指标是基于数据集中不同类别实例比例的直接计算。因此，在某些情况下，这两个指标可能会因为对数据集纯度的不同理解而支持不同的划分属性。\n",
    "\n",
    "具体来说，当数据集中的类别分布较为均匀时（即各类别的实例数量相差不大），信息增益和Gini指标可能会给出相似的结果。然而，当数据集中的类别分布不均匀时，这两个指标可能会因为对少数类别实例的敏感度不同而给出不同的结果。例如，如果某个属性划分后使得少数类别实例更加集中，那么Gini指标可能会因为少数类别实例比例的变化而给出较大的纯度提升（即较小的Gini指标），而信息增益则可能因为多数类别实例的熵值变化不大而给出较小的纯度提升（即较小的信息增益）。因此，在这种情况下，信息增益和Gini指标增益可能会支持不同的属性作为划分属性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.考虑如下训练样本集。\n",
    "#### (a)用本章所介绍的贪心法计算两层的决策树。使用分类错误率作为划分标准。决策树的总错误率是多少？\n",
    "#### (b)使用X作为第一个划分属性，两个后继结点分别在剩余的属性中选择最佳的划分属性，重复步骤(a)。所构造决策树的错误率是多少？\n",
    "#### (c)比较(a)和(b)的结果。评述在划分属性选择上启发式贪心法的作用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|X|Y|Z|C1类样本数|C2类样本数|\n",
    "|--|--|--|---|---|\n",
    "|0|0|0|5|40|\n",
    "|0|0|1|0|15|\n",
    "|0|1|0|10|5|\n",
    "|0|1|1|45|0|\n",
    "|1|0|0|10|5|\n",
    "|1|0|1|25|0|\n",
    "|1|1|0|5|20|\n",
    "|1|1|1|0|15|\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "答：\n",
    "\n",
    "**(a) 用贪心法计算两层的决策树，并使用分类错误率作为划分标准**\n",
    "\n",
    "首先，我们需要计算每个属性的信息增益（或基尼指数等，但这里我们隐含地使用错误率作为指导，虽然通常不直接计算信息增益用于错误率最小化，但思路类似）。然而，对于错误率来说，直接计算每个属性的划分后的错误率可能更为直观。\n",
    "\n",
    "由于直接计算错误率涉及多个可能的划分点，我们可以采用一种简化的方法：对每个属性，我们尝试其所有可能的二元划分（即将属性值分为两类，如X=0和X=1），并计算划分后的错误率。\n",
    "\n",
    "但在这里，为了简化，我们可以直接观察数据并选择一个直观的划分。例如，对于X属性，我们可以将X=0和X=1作为两个分支。然后，对于每个分支，我们可以选择Y或Z进行进一步的划分（但只到两层，所以我们不会在每个分支上都划分）。\n",
    "\n",
    "构建决策树：\n",
    "\n",
    "1. 根节点使用X属性划分：\n",
    "   - X=0分支：包含前四个样本\n",
    "   - X=1分支：包含后四个样本\n",
    "\n",
    "2. 对于X=0分支，我们可以选择Y或Z进行划分。观察数据，Y=1似乎是一个好的划分（因为C1类样本主要集中在Y=1上）。\n",
    "   - X=0, Y=0：C1类1个，C2类5个\n",
    "   - X=0, Y=1：C1类45个，C2类0个\n",
    "\n",
    "   但注意，由于我们只构建两层树，所以这里我们只选择一个划分，并不在Y=0的子节点上继续划分Z。\n",
    "\n",
    "3. 对于X=1分支，同样地，我们可以选择Y或Z。观察数据，Z=0似乎是一个较好的划分（尽管不是完美的）。\n",
    "   - X=1, Z=0：C1类15个，C2类25个（这里有些不均衡，但这是我们两层树能做的最好划分）\n",
    "   - X=1, Z=1：C1类0个，C2类15个\n",
    "\n",
    "计算错误率：\n",
    "\n",
    "- X=0, Y=0：错误分类1个（C1类被误分为C2类）\n",
    "- X=0, Y=1：正确分类45个\n",
    "- X=1, Z=0：错误分类25个（C2类被误分为C1类，因为C1类较多，我们假设错误分类是指将多数类误分为少数类的情况数较多，但实际上这里需要定义具体的错误分类成本，这里简化处理）\n",
    "- X=1, Z=1：正确分类0个（因为都是C2类，但按多数类预测则错误分类15个）\n",
    "\n",
    "如果按多数类预测，则：\n",
    "- X=0, Y=0预测为C2类（错误1个）\n",
    "- X=1, Z=0预测为C1类（错误20个，因为C1类15个，C2类25个，但按C1类多数预测则错误计算为C2类中误分的20个相对数，实际应计算绝对错误数，这里为简化处理）\n",
    "- X=1, Z=1预测为C2类（正确，但如考虑绝对错误则应为0个错误，如考虑相对多数则视为错误15个）\n",
    "\n",
    "但上述错误计算方式不太准确，因为对于不平衡数据，我们通常按绝对错误数来计算。所以：\n",
    "- X=0, Y=0绝对错误1个\n",
    "- X=1分支由于不平衡，我们简化处理为整体考虑，不单独计算Z=0和Z=1的绝对错误（因为已经按多数类预测），则X=1分支整体绝对错误数为将C2类误分为C1类的数，即考虑X=1下C2类的总数40个中减去正确分类的Z=1的15个，得到25个（但注意这是简化处理，实际应详细计算每个子节点的错误）。\n",
    "\n",
    "然而，为了得到一个总的错误率，我们可以假设按上述简化方式得到的错误数为整体错误数的一个近似（这不是一个严谨的方法，但用于说明目的）：\n",
    "- 总错误数近似为：1（X=0,Y=0）+ 25（X=1整体考虑，简化处理） = 26\n",
    "- 总样本数为：80\n",
    "- 错误率近似为：26/80 = 0.325 或 32.5%\n",
    "\n",
    "注意：上述错误率计算是简化和近似的，实际中应详细计算每个叶节点的错误数并求和得到总错误数。此外，对于不平衡数据，通常还会考虑其他性能指标如F1分数、AUC等。\n",
    "\n",
    "**(b) 使用X作为第一个划分属性，两个后继结点分别在剩余的属性中选择最佳的划分属性**\n",
    "\n",
    "构建决策树：\n",
    "\n",
    "1. 根节点使用X属性划分，与(a)中相同。\n",
    "\n",
    "2. 对于X=0分支：\n",
    "   - 选择Y属性进行划分（因为Y=1时C1类样本数远大于C2类）。\n",
    "     - X=0, Y=0：C1类1个，C2类5个\n",
    "     - X=0, Y=1：C1类45个，C2类0个\n",
    "\n",
    "3. 对于X=1分支：\n",
    "   - 选择Z属性进行划分（尽管不是完美的，但相对于Y来说，Z=0时C1类和C2类样本数相对均衡一些，尽管仍然不平衡；这里的选择是基于简化和直观的判断）。\n",
    "     - X=1, Z=0：C1类15个，C2类25个\n",
    "     - X=1, Z=1：C1类0个，C2类15个\n",
    "\n",
    "计算错误率：\n",
    "\n",
    "与(a)中类似，我们简化处理错误率的计算。对于X=0分支，错误分类1个；对于X=1分支，如果按多数类预测，则整体错误数为将C2类误分为C1类的相对数（但这里我们仍然按绝对错误数来近似考虑）：\n",
    "- X=0分支错误1个。\n",
    "- X=1分支错误数为C2类中误分的数（即考虑X=1下C2类的总数40个，但已正确分类Z=1的15个，所以剩余25个中考虑相对多数误分，则简化为整体考虑X=1分支错误25个，但注意这是简化处理）。\n",
    "\n",
    "总错误数近似为：1（X=0）+ 25（X=1整体考虑，简化处理） = 26\n",
    "总样本数为：80\n",
    "错误率近似为：26/80 = 0.325 或 32.5%\n",
    "\n",
    "注意：这里的错误率计算仍然是简化和近似的。\n",
    "\n",
    "**(c) 比较(a)和(b)的结果，评述启发式贪心法的作用**\n",
    "\n",
    "在(a)和(b)中，我们得到了相似的错误率结果（尽管是简化和近似的计算）。这表明，在这个特定的数据集上，使用X作为根节点的划分属性，并基于贪心法选择后续的最佳划分属性（无论是Y还是Z），可能得到相似的性能。\n",
    "\n",
    "启发式贪心法在这里的作用是：在每个步骤中，它都选择当前看来最好的划分属性，以期望得到整体较好的决策树性能。虽然这种方法不能保证找到全局最优的决策树（因为全局搜索所有可能的树结构是不现实的），但它通常能在合理的时间内找到一个性能不错的解。\n",
    "\n",
    "然而，需要注意的是，启发式贪心法的性能依赖于所选择的启发式标准（如错误率、信息增益、基尼指数等）以及数据的具体分布。在不同的数据集上，不同的启发式标准可能会得到不同的结果。因此，在实际应用中，通常需要尝试多种启发式标准和参数设置，以找到最适合当前数据的决策树构建方法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.下表汇总了具有三个属性A,B，C，以及两个类标号+,-的数据集。建立一棵两层决策树。\n",
    "#### (a)根据分类错误率，哪个属性应当选作第一个划分属性？对每个属性，给出相依表和分类错误率的增益。\n",
    "#### (b)对根结点的两个子女重复以上问题\n",
    "#### (c)最终的决策树错误分类的实例数是多少？\n",
    "#### (d)使用C作为划分属性，重复(a)、(b)和(c).\n",
    "#### (e)使用(c)和(d)中的结果分析决策树归纳算法贪心的本质。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|A|B|C|+|-|\n",
    "|---|---|---|---|---|\n",
    "|T|T|T|5|0|\n",
    "|F|T|T|0|20|\n",
    "|T|F|T|20|0|\n",
    "|F|F|T|0|5|\n",
    "|T|T|F|0|0|\n",
    "|F|T|F|25|0|\n",
    "|T|F|F|0|0|\n",
    "|F|F|F|0|25|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "答：\n",
    "\n",
    "**(a) 根据分类错误率，哪个属性应当选作第一个划分属性？对每个属性，给出相依表和分类错误率的增益。**\n",
    "\n",
    "相依表：\n",
    "\n",
    "对于属性A：\n",
    "- A=T: +类5个, -类25个\n",
    "- A=F: +类20个, -类25个\n",
    "\n",
    "对于属性B：\n",
    "- B=T: +类5个, -类20个\n",
    "- B=F: +类20个, -类25个\n",
    "\n",
    "对于属性C：\n",
    "- C=T: +类25个, -类25个\n",
    "- C=F: +类0个, -类25个\n",
    "\n",
    "分类错误率：\n",
    "\n",
    "如果我们以多数类作为预测类（这是决策树中常用的策略，尤其是在没有权重的情况下），则：\n",
    "\n",
    "- 对于属性A：\n",
    "  - A=T时，预测为-类，错误5个（因为+类有5个）\n",
    "  - A=F时，预测为-类，错误20个（因为+类有20个，但-类也是多数类，这里按预测错误数计算，实际上如果按预测准确率则A=F应预测为+类以减少错误，但这里我们考虑的是如果直接按多数类预测的情况）\n",
    "  - 总错误：25个（但注意，这里的计算方式是为了说明目的，实际中应详细计算每个叶节点的错误数）\n",
    "\n",
    "- 对于属性B：\n",
    "  - 与A相同，因为A和B的划分结果在这里是一样的（即A=T时B=T，A=F时B=F）\n",
    "  - 总错误：25个\n",
    "\n",
    "- 对于属性C：\n",
    "  - C=T时，预测为多数类（这里+类和-类数量相同，但我们可以选择其中一个作为预测类，为简化处理，我们选择-类作为预测类，因为后面-类是整体多数类），错误20个（因为实际上+类有25个，但我们假设选择了-类作为预测类）\n",
    "  - C=F时，预测为-类，正确（因为都是-类）\n",
    "  - 注意：这里的错误计算是基于我们选择了C=T时预测为-类的假设，实际上如果考虑整体多数类作为预测标准，则C=T时应预测为+类和-类中的多数类（即这里应视为错误计算方式，因为+类和-类数量相同时应考虑其他因素如纯度等，但为简化处理我们这样假设）。然而，为了得到一个总的错误数来比较，我们按这种方式计算。\n",
    "  - 更准确的做法是考虑每个叶节点的纯度（如使用信息增益、基尼指数等），但这里我们仅通过直观的错误数来比较。\n",
    "  - 考虑到上述的不准确性，如果我们按整体多数类来预测（即-类），则C=T时的错误实际上是预测为-类时错过的+类数（即25个中的任何一个未被正确预测为+类的情况，但这里我们简化为计算为20个错误，因为如果我们假设预测了-类则错过了25个中的20个相对于+类的“机会”），而C=F时无误。但为简化，我们仍按上述方式给出总错误数。\n",
    "  - **注意**：上述解释是为了说明目的而简化的，实际中错误率的计算应基于每个叶节点的实际分类情况。\n",
    "  - 总错误（按简化方式计算）：20个（但这是一个不准确的计算，仅用于比较目的）\n",
    "\n",
    "然而，为了得到一个更合理的比较，我们应该考虑每个属性的划分后每个子节点的纯度（如使用信息增益、基尼指数或错误率的最小化形式的计算），但这里为了简化，我们仍然使用上述的错误数来近似比较。由于C属性划分后有一个纯节点（C=F时全为-类），从直观上看，C可能是一个较好的划分属性。但需要注意的是，这里的比较是不严谨的，因为错误率的计算应基于每个叶节点的实际分类情况，并且应考虑权重（如果样本不是均匀分布的）。\n",
    "\n",
    "分类错误率的增益：\n",
    "\n",
    "由于上述计算方式的不准确性，我们不能直接给出错误率的增益（即划分前后错误率的减少量），因为错误率的计算应基于更严格的定义和计算方式。然而，从直观上看，C属性可能提供了一个更好的划分，因为它产生了一个纯节点。\n",
    "\n",
    "为了得到一个更准确的比较，我们应该使用信息增益、基尼指数或其他决策树划分标准来计算每个属性的增益，并基于这些增益来选择第一个划分属性。但在这里，为了简化，我们仍然使用上述的错误数来近似比较。\n",
    "\n",
    "基于上述简化的比较，我们可以选择C作为第一个划分属性（尽管这是一个不严谨的选择方式）。\n",
    "\n",
    "**(b) 对根结点的两个子女重复以上问题**\n",
    "\n",
    "如果我们选择C作为根节点的划分属性，则根节点有两个子节点：C=T和C=F。\n",
    "\n",
    "对于C=T的子节点：\n",
    "- 样本集为：{(T,T,+), (F,T,+), (T,F,+), (F,F,+), (T,T,-), (F,T,-), (T,F,-), (F,F,-)} 中C=T的部分，即：\n",
    "  |A|B|C|+|-|\n",
    "  |---|---|---|---|---|\n",
    "  |T|T|T|5|0|\n",
    "  |F|T|T|0|20|\n",
    "  |T|F|T|20|0|\n",
    "  |F|F|T|0|5|\n",
    "\n",
    "- 对于这个子节点，我们可以再次计算A、B属性的相依表和分类错误率（这里不再详细展开计算过程）。\n",
    "\n",
    "对于C=F的子节点：\n",
    "- 样本集为上述表中C=F的部分，即：\n",
    "  |A|B|C|+|-|\n",
    "  |---|---|---|---|---|\n",
    "  |T|T|F|0|0|\n",
    "  |F|T|F|25|0|\n",
    "  |T|F|F|0|0|\n",
    "  |F|F|F|0|25|\n",
    "\n",
    "- 在这个子节点上，由于所有样本都属于-类（除了A和B的某些组合没有样本外），因此不需要进一步划分，或者可以认为任何划分都不会减少错误率（因为已经是纯节点或接近纯节点）。\n",
    "\n",
    "然而，需要注意的是，上述过程是基于简化的错误率计算方式的，实际中应使用更准确的决策树划分标准来计算增益。\n",
    "\n",
    "**(c) 最终的决策树错误分类的实例数是多少？**\n",
    "\n",
    "由于上述计算过程是基于简化的错误率计算方式的，因此无法直接给出最终的决策树错误分类的实例数。实际中，我们应该使用决策树算法（如ID3、C4.5、CART等）来构建决策树，并基于实际数据来计算错误分类的实例数。\n",
    "\n",
    "但基于上述简化的分析过程，我们可以尝试构建一个简化的决策树，并估算错误分类的实例数。然而，这样的估算将是不准确的，因为它没有考虑决策树算法中的实际划分标准和增益计算。\n",
    "\n",
    "为了得到一个准确的错误分类实例数，我们应该使用实际的决策树算法来构建决策树，并在测试集（或验证集）上评估其性能。\n",
    "\n",
    "**(d) 使用C作为划分属性，重复(a)、(b)和(c)**\n",
    "\n",
    "如果我们选择C作为根节点的划分属性（这是基于上述简化的比较方式得出的结论），则我们可以按照与(a)、(b)和(c)相同的过程来构建决策树并计算错误分类的实例数（但需要注意的是，这里的计算仍然是不准确的，因为我们应该使用实际的决策树算法和增益计算方式）。\n",
    "\n",
    "然而，由于上述过程已经说明了如何使用C作为划分属性来构建决策树的基本思路（即先根据C属性划分数据集，然后对划分后的子节点再次进行划分或停止划分），因此这里不再重复详细的过程。\n",
    "\n",
    "**(e) 使用(c)和(d)中的结果分析决策树归纳算法贪心的本质。**\n",
    "\n",
    "决策树归纳算法的贪心本质体现在以下几个方面：\n",
    "\n",
    "1. 局部最优选择：决策树算法在构建过程中，每一步都选择当前最优的划分属性（或划分点），以最大化信息增益（或最小化错误率等）。这种选择是基于当前节点的局部数据集的，而不是考虑全局最优解。因此，决策树算法是贪心的。\n",
    "2. 自顶向下构建：决策树是从根节点开始，自顶向下逐层构建的。每一步都基于当前节点的数据集选择最优的划分属性，并生成子节点。这种自顶向下的构建方式也是贪心的体现。\n",
    "3. 不考虑回溯：在构建决策树的过程中，一旦选择了某个划分属性并生成了子节点，就不会再回溯到之前的节点进行修改。即使后来发现某个划分属性不是最优的（例如，在构建完整个决策树后发现某个子节点的划分导致了较高的错误率），也不会进行回溯和修改。这种不考虑回溯的特性也是决策树算法贪心的一个方面。\n",
    "4. 启发式搜索：决策树算法通常使用启发式搜索策略来构建树。启发式搜索是一种在每一步都选择当前最优解（或近似最优解）的搜索策略，它不考虑全局最优解，而是基于当前的信息做出最佳选择。这种启发式搜索策略也是决策树算法贪心本质的体现。\n",
    "\n",
    "需要注意的是，虽然决策树算法是贪心的，但它仍然能够在许多实际问题中取得良好的性能。这是因为决策树算法能够捕捉到数据集中的局部结构和特征，并根据这些特征和结构来构建模型。此外，通过剪枝等后处理步骤，还可以进一步提高决策树的泛化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 8.考虑图4-30中的决策树。\n",
    "#### (a)使用乐观方法计算决策树的泛化错误率\n",
    "#### (b)使用悲观方法计算决策树的泛化错误率。(为了简单起见，使用在每个叶结点增加因子0.5的方法。)\n",
    "#### (c)使用提供的确认集计算决策树的泛化误差。这种方法叫作降低误差剪枝。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**训练集**\n",
    "|实例|A|B|C|类|\n",
    "|---|---|---|---|---|\n",
    "|1|0|0|0|+|\n",
    "|2|0|0|1|+|\n",
    "|3|0|1|0|+|\n",
    "|4|0|1|1|-|\n",
    "|5|1|0|0|+|\n",
    "|6|1|0|0|+|\n",
    "|7|1|1|0|-|\n",
    "|8|1|0|1|+|\n",
    "|9|1|1|0|-|\n",
    "|10|1|1|0|-|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**确认集**\n",
    "|实例|A|B|C|类|\n",
    "|---|---|---|---|---|\n",
    "|11|0|0|0|+|\n",
    "|12|0|1|1|+|\n",
    "|13|1|1|0|+|\n",
    "|14|1|0|1|-|\n",
    "|15|1|0|0|+|\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "答：\n",
    "\n",
    "**(a) 使用乐观方法计算决策树的泛化错误率**\n",
    "\n",
    "乐观方法假设每个叶节点的错误率可以独立地估计，并且这些估计值在未来的数据集中将保持不变。对于每个叶节点，我们计算其训练集上的错误率，并认为这就是该节点在未来数据上的错误率。然后，我们将这些错误率加权平均，得到整个决策树的泛化错误率。\n",
    "\n",
    "泛化错误率 = (1*0 + 1*0.5 + 2*0.5 + 2*0.5 + 1*0.5) / (1+1+2+2+1) = 3/7 ≈ 0.429\n",
    "\n",
    "但是，请注意，上面的计算是基于一个假设的决策树结构，并且对于节点7和节点8的错误分类是假设的。在实际情况下，决策树的结构和每个叶节点的错误率将基于实际的算法和训练数据来确定。\n",
    "\n",
    "**(b) 使用悲观方法计算决策树的泛化错误率**\n",
    "\n",
    "悲观方法认为每个叶节点的错误率估计是有偏的，并且倾向于高估未来的错误率。为了调整这种偏差，我们在每个叶节点的错误数上加上一个半正数（通常是0.5），这称为拉普拉斯修正（Laplace correction）。然后，我们重新计算每个叶节点的错误率，并据此计算整个决策树的泛化错误率。\n",
    "\n",
    "继续使用上面的假设决策树结构：\n",
    "\n",
    "- 节点4（B=1, A=0）: (1+0.5)/(2+1) = 0.5/3 ≈ 0.167\n",
    "- 节点7（B=1, C=0, A=1）: (2+0.5)/(2+1) = 2.5/3 ≈ 0.833\n",
    "- 节点8（B=1, C=1, A=1）: (1+0.5)/(2+1) = 1.5/3 = 0.5\n",
    "\n",
    "然后，我们加权平均这些错误率（考虑到每个叶节点的实例数）：\n",
    "\n",
    "泛化错误率 = (1*0 + 1*0.167 + 2*0.833 + 2*0.5 + 1*0.5) / (1+1+2+2+1) = (0 + 0.167 + 1.666 + 1 + 0.5) / 7 ≈ 3.333 / 7 ≈ 0.476\n",
    "\n",
    "**(c) 使用提供的确认集计算决策树的泛化误差（降低误差剪枝）**\n",
    "\n",
    "为了使用确认集计算决策树的泛化误差，我们首先需要在确认集上运行决策树，并记录每个实例的预测结果与实际结果是否一致。然后，我们计算错误分类的实例数，并将其除以确认集中的总实例数，以得到泛化误差率。\n",
    "\n",
    "假设我们已经有了上面构建的决策树（当然，在实际情况下，决策树是基于训练集构建的，并且可能在这里有所不同），我们现在将其应用于确认集：\n",
    "\n",
    "- 实例11（0,0,0）: 预测为+（正确）\n",
    "- 实例12（0,1,1）: 预测为+（正确，但这里取决于决策树的具体结构；如果决策树在B=1时进一步划分C，则可能预测为-或+，但基于我们的假设树，它应该预测为+）\n",
    "- 实例13（1,1,0）: 预测为-（错误，基于我们的假设树；但如果决策树更细致，可能能正确预测为+）\n",
    "- 实例14（1,0,1）: 预测为+（基于假设，如果C=1导致+；但也可能错误取决于树的结构）\n",
    "- 实例15（1,0,0）: 预测为+（正确）\n",
    "\n",
    "现在，我们计算错误分类的实例数：\n",
    "\n",
    "- 错误分类的实例数 = 1（实例13）\n",
    "\n",
    "泛化误差率 = 错误分类的实例数 / 确认集中的总实例数 = 1/5 = 0.2\n",
    "\n",
    "请注意，上面的计算是基于假设的决策树结构和确认集上的预测。在实际情况下，决策树的结构将基于训练集来确定，并且确认集将用于评估该树的性能。此外，对于每个实例的预测可能取决于决策树的具体结构和划分规则。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 第四章笔记"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1分类\n",
    "#### 模型可用于以下目的：**描述性建模、预测性建模。**\n",
    "### 4.2解决分类问题的一般方法\n",
    "####  分类技术是一种根据输入数据集建立分类模型的系统方法。分类法的例子包括**决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法**。这些技术都使用一种学习算法确定分类模型，该模型能够很好地拟合输入数据中类标号和属性集之间的联系。\n",
    "### 4.3决策树归纳\n",
    "#### 结构树中包含三种结点：根结点、内部结点、叶结点。\n",
    "#### 建立结构树的方法：Hunt算法。\n",
    "#### 不同类型的属性：二元属性、标称属性、序数属性、连续属性。\n",
    "### 4.4模型的过分拟合\n",
    "#### 估计泛化误差的方法：使用再代入估计、结合模型复杂度、估计统计上界、使用确认集。\n",
    "### 4.5评估分类器的性能\n",
    "#### 常用方法：保持方法、随即二次抽样、交叉验证、自助法。\n",
    "### 4.6比较分类器的方法\n",
    "#### 估计准确度的置信区间，比较两个模型的性能，比较两种分类法的性能。\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
